struct Solution;

impl Solution {
    fn rob_ii(nums: Vec<i32>) -> i32 {
        if nums.is_empty() {
            return 0;
        }

        if nums.len() == 1 {
            return nums[0];
        }

        let len = nums.len();
        let (include1, exclude1) = Solution::rob_sub(&nums[1..]);
        let (include2, exclude2) = Solution::rob_sub(&nums[0..len - 1]);
        *[include1, exclude1, include2, exclude2].iter().max().unwrap()
    }

    fn rob_sub(nums: &[i32]) -> (i32, i32) {
        if nums.is_empty() {
            return (0, 0);
        }
        let (include, exclude) = Solution::rob_sub(&nums[1..]);

        (
            // include
            nums[0] + exclude,
            // exclude
            i32::max(include, exclude)
        )
    }
}

fn main() {
    Solution::rob_ii(vec![]);
}
